/*
 * 三叉链表结构存储二叉树
 */
package com.yuan.algorithms.arithmetic_1;

public class BinTreeNode {
	private Object data;//数据域
	private BinTreeNode parent;//父节点
	private BinTreeNode lChild;//左孩子
	private BinTreeNode rChild;//右孩子
	private int height;//以该结点为根的子树的高度
	private int size;//该结点子孙数（包括节点本身）
	
	public BinTreeNode() {
		this(null);
	}
	public BinTreeNode(Object e) {
		data = e;
		height = 0;
		size = 1;
		parent = lChild = rChild = null;
	}
	
	/**
	 * 获取数据
	 * @return
	 */
	public Object getData() {
		return data;
	}
	
	/**
	 * 设置数据
	 * @param data
	 */
	public void setData(Object data) {
		this.data = data;
	}
	
	/****判断当前结点的位置情况****/
	/**
	 * 判断是否有父亲
	 * @return
	 */
	public boolean hasParent() {
		return parent != null;
	}
	
	/**
	 * 判断是否有左孩子
	 * @return
	 */
	public boolean hasLChild() {
		return lChild != null;		
	}
	
	/**
	 * 判断是否有右孩子
	 * @return
	 */
	public boolean hasRChild() {
		return rChild != null;		
	}
	
	/**
	 * 判断是否是叶子结点
	 * @return
	 */
	public boolean isLeaf() {
		return !hasLChild() && !hasRChild();
	}
	
	/**
	 * 判断是否是某结点的左孩子
	 * @return
	 */
	public boolean isLChild() {
		return (hasLChild() && this==parent.lChild);
	}
	
	/**
	 * 判断是否是某结点的右孩子
	 * @return
	 */
	public boolean isRChild() {
		return (hasRChild() && this==parent.rChild);
	}
	
	/****与height有关的方法****/
	
	/**
	 * 取结点的高度，即以该结点为根的树的高度
	 * @return
	 */
	public int getHeight() {
		return height;
	}
	
	/**
	 * 更新当前结点及其祖先的高度
	 */
	public void updateHeight() {
		int newH = 0;//新高度初始化为0，高度等于左右子树高度加1中的大者
		if (hasLChild()) {
			newH = Math.max(newH, 1 + getLChild().getHeight());
		}
		if (hasRChild()) {
			newH = Math.max(newH, 1 + getRChild().getHeight());
		}
		if (newH==height) {
			//高度没有发生变化则直接返回
			return;
		}
		height = newH;
		if (hasParent()) {
			//递归更新祖先的高度
			getParent().updateHeight();
		}
	}
	
	/****与parent相关的方法****/
	
	/**
	 * 取父结点
	 * @return
	 */
	public BinTreeNode getParent() {
		return parent;
	}
	
	/**
	 * 断开与父亲的关系
	 */
	public void sever() {
		if (!hasParent()) {
			return;
		}
		if (isLChild()) {
			parent.lChild = null;
		}else {
			parent.rChild = null;
		}
		parent.updateHeight();
		parent.updateSize();
		parent = null;
	}
	
	/****与Child有关的方法****/
	
	/**
	 * 取左孩子
	 * @return
	 */
	public BinTreeNode getLChild() {
		return lChild;
	}
	
	/**
	 * 取右孩子
	 * @return
	 */
	public BinTreeNode getRChild() {
		return rChild;
	}
	
	/**
	 * 设置当前结点的左孩子，返回原左孩子
	 * @param lc
	 * @return
	 */
	public BinTreeNode setLChild(BinTreeNode lc) {
		BinTreeNode oldLC = this.lChild;
		if (hasLChild()) {
			lChild.sever();//断开当前左孩子与结点的关系
		}
		if (lc != null) {
			lc.sever();//断开lc与其父节点的关系
			this.lChild = lc;//确立父子关系
			lc.parent = this;
			this.updateHeight();//更新当前节点及其祖先高度
			this.updateSize();//更新当前节点及其祖先规模
		}
		return oldLC;
	}
	
	/**
	 * 设置当前结点的右孩子，返回原右孩子
	 * @param rc
	 * @return
	 */
	public BinTreeNode setRChild(BinTreeNode rc) {
		BinTreeNode oldRC = this.rChild;
		if (hasRChild()) {
			rChild.sever();//断开当前右孩子与结点的关系
		}
		if (rc != null) {
			rc.sever();//断开rc与其父节点的关系
			this.rChild = rc;//确立父子关系
			rc.parent = this;
			this.updateHeight();//更新当前节点及其祖先高度
			this.updateSize();//更新当前节点及其祖先规模
		}
		return oldRC;
	}
	
	/****与size有关的方法****/
	
	/**
	 * 取以该结点为根的树的结点数
	 * @return
	 */
	public int getSize() {
		return size;
	}
	
	/**
	 * 更新当前结点及其祖先的子孙数
	 */
	public void updateSize() {
		size = 1;//初始化为1（结点本身）
		if (hasLChild()) {
			size += getLChild().getSize();//加上左子树规模
		}
		if (hasRChild()) {
			size += getRChild().getSize();//加上右子树规模
		}
		if (hasParent()) {
			getParent().updateHeight();//递归更新祖先的规模
		}
	}
	
}
